package main

import (
	"fmt"
	"math"
)

type l struct {
	root *node
	last *node
}

func (l l) Root() *node {
	return l.root
}

func newL() *l {
	return &l{root: nil, last: nil}
}

func (l *l) PushBack(value int) {
	if l.last == nil {
		l.root = newNode(value)
		l.last = l.root
	} else {
		l.last.next = newNode(value)
		l.last = l.last.next
	}
}

type node struct {
	value int
	next  *node
}

func newNode(value int) *node {
	return &node{value: value, next: nil}
}

//求2个可能有环的链表的相交节点，没有则返回nil

func main() {
	// 1->2->3->4->5->6->7->null

	head1 := newNode(1)
	head1.next = newNode(2)
	head1.next.next = newNode(3)
	head1.next.next.next = newNode(4)
	head1.next.next.next.next = newNode(5)
	head1.next.next.next.next.next = newNode(6)
	head1.next.next.next.next.next.next = newNode(7)

	// 0->9->8->6->7->null
	head2 := newNode(0)
	head2.next = newNode(9)
	head2.next.next = newNode(8)
	head2.next.next.next = head1.next.next.next.next.next // 8->6
	la := newL()
	lb := newL()
	la.root = head1
	lb.root = head2
	fmt.Println(solve(la, lb).value)

	// 1->2->3->4->5->6->7->4...
	head1 = newNode(1)
	head1.next = newNode(2)
	head1.next.next = newNode(3)
	head1.next.next.next = newNode(4)
	head1.next.next.next.next = newNode(5)
	head1.next.next.next.next.next = newNode(6)
	head1.next.next.next.next.next.next = newNode(7)
	head1.next.next.next.next.next.next = head1.next.next.next // 7->4

	// 0->9->8->2...
	head2 = newNode(0)
	head2.next = newNode(9)
	head2.next.next = newNode(8)
	head2.next.next.next = head1.next // 8->2
	la.root = head1
	lb.root = head2
	fmt.Println(solve(la, lb).value)

	// 0->9->8->6->4->5->6..
	head2 = newNode(0)
	head2.next = newNode(9)
	head2.next.next = newNode(8)
	head2.next.next.next = head1.next.next.next.next.next // 8->6
	la.root = head1
	lb.root = head2
	fmt.Println(solve(la, lb).value)

}

// 1 判断a，b是否有环，并返回入环节点
func getLoopInsert(l *l) *node {

	//保证至少3个节点
	if l.root == nil || l.root.next == nil || l.root.next.next == nil {
		return nil
	}

	//1 先让slow和fast相遇，如果无法相遇 则无环
	slow := l.root.next
	fast := l.root.next.next

	for fast != slow {
		if fast.next == nil || fast.next.next == nil {
			return nil
		}
		slow = slow.next
		fast = fast.next.next
	}
	//无环的情况

	//	有环的情况 寻找入环点
	//2 fast回到root,2者同时前进直到相交
	fast = l.root
	for slow != fast {
		fast = fast.next
		slow = slow.next
	}

	return slow
}

// 主函数，获得两链表的相交节点
func solve(la, lb *l) *node {
	loop1 := getLoopInsert(la)
	loop2 := getLoopInsert(lb)

	if loop1 == nil && loop2 == nil {
		return noLoop(la, lb)
	}

	if loop1 != nil && loop2 != nil {
		return bothLoop(la, lb, loop1, loop2)
	}
	return nil
}

// 当两链表都无环 判断是否相交，并返回相交点
func noLoop(la, lb *l) *node {
	//	1 判断a，b是否相交
	end1 := la.root
	n := 0 //记录两链表长度差
	for end1.next != nil {
		end1 = end1.next
		n++
	}

	end2 := lb.root
	for end2.next != nil {
		end2 = end2.next
		n--
	}

	//a,b不相交
	if end1 != end2 {
		return nil
	}

	//	2 长的链表指针先走
	var cur1 *node //指向长链表的头节点
	var cur2 *node
	if n > 0 {
		cur1 = la.root
	} else {
		cur1 = lb.root
	}

	if cur1 != la.root {
		cur2 = la.root
	} else {
		cur2 = lb.root
	}
	//cur1先走
	for i := 0; i < int(math.Abs(float64(n))); i++ {
		cur1 = cur1.next
	}

	//	cur1和cur2一起走，返回相交点
	for cur1 != cur2 {
		cur1 = cur1.next
		cur2 = cur2.next
	}
	return cur1
}

// a,b都有环
func bothLoop(la, lb *l, loop1, loop2 *node) *node {
	//	2)a,b相交点在入环点前或入环点，入环点相同，
	if loop1 == loop2 {
		len1 := 1
		p1 := la.root
		for p1 != loop1 {
			len1++
			p1 = p1.next
		}

		len2 := 1
		p1 = lb.root
		for p1 != loop1 {
			len2++
			p1 = p1.next
		}
		var cur1 *node
		var cur2 *node
		if len1 > len2 {
			cur1 = la.root
		} else {
			cur1 = lb.root
		}
		if cur1 != la.root {
			cur2 = la.root
		}

		for i := 0; i < int(math.Abs(float64(len1-len2))); i++ {
			cur1 = cur1.next
		}

		for cur1 != cur2 {
			cur1 = cur1.next
			cur2 = cur2.next
		}

		return cur1
	}

	//	1,3) a,b不相交，或a，b相交，入环点在环的不同位置
	p1 := loop1.next

	for p1 != loop2 {
		if p1 == loop1 { //如果p1回到了loop1 则不相交
			return nil
		}
		p1 = p1.next
	}
	return loop1

}
